package hot;

import java.util.HashMap;
import java.util.Map;

public class wuliuling {
//    https://leetcode.cn/problems/subarray-sum-equals-k/submissions/?envType=study-plan-v2&envId=top-100-liked

//        public static int subarraySum(int[] nums, int k) {
//            int count=0;
//            for(int i=0;i<nums.length;i++){
//                int sum=0;
//                for(int j=i;j<nums.length;j++){
//                    sum+=nums[j];
//                    if(sum==k){
//                        count++;
//                        continue;
//                    }
//                }
//            }
//            return count;
//        }

    public static int subarraySum(int[] nums, int k) {
        int n=nums.length;
        //开一个前缀和数组
        int[] prefixsumarray=new int[n];
        //创建哈希表
        Map<Integer,Integer> prefixsummap=new HashMap<>();
        int count=0;
        for(int i=0;i<n;i++){
            if(i==0){
                prefixsumarray[i]=nums[i];
            }else{
                prefixsumarray[i]=prefixsumarray[i-1]+nums[i];
            }
             if(prefixsumarray[i]==k){
                 count++;
             }
            if(prefixsummap.containsKey(prefixsumarray[i]-k)){
                count+=prefixsummap.get(prefixsumarray[i]-k);
            }
            prefixsummap.put(prefixsumarray[i],prefixsummap.getOrDefault(prefixsumarray[i],0)+1);

        }
        return count;
    }



    public static void main(String[] args) {
        int[] nums={1};
        int i = subarraySum(nums, 0);
        System.out.println(i);

    }
    }

